/**
 * Created with IntelliJ IDEA.
 * Description:
 * https://gitee.com/li--jiaqiang/java-test.git
 * git pull
 * git pull origin master
 * git pull origin master --allow-unrelated-histories
 * User: 86187
 * Date: 2022-04-26
 * Time: 20:45
 */

//Scanner scan = new Scanner(System.in);

import java.util.Arrays;

public class TestDemo3 {

    /**
     * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
     *
     * 示例 1：
     * 输入：nums = [1,2,0]
     * 输出：3
     *
     * 示例 2：
     * 输入：nums = [3,4,-1,1]
     * 输出：2
     *
     * 示例 3：
     * 输入：nums = [7,8,9,11,12]
     * 输出：1
     * @param nums
     * @return
     */
    public static int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);//排为升序
        if(nums.length == 1) {
            return (nums[0]-1 == 0) ? 2 : 1;
        }

        int q = 1;
        int k = 0;
        int count = 0;
        //0 1 1 2 2
        while(q < nums.length) {
            if(nums[q] > 0) {
                count++;
                if(count == 1) {
                    k = nums[q-1] > 0 ? q-1: q; //找第一个大于0的数
                }
                //两个数均为正数且相减不等于1，此时只要第一个正数不是1，就返回减数+1
                if(nums[q] - nums[q-1] > 1 && nums[q-1] > 0 && nums[k] == 1) {
                    return nums[q-1]+1;
                }
            }
            q++;
        }
        //走到这说明从第一个正数之后都是连续的正数
        //第一个正数不是1就返回最后一个正数+1
        //否则返回1
        return nums[k] == 1 ? nums[q-1]+1 : 1;
    }

    public static void main(String[] args) {
        int[] nums = {7,8,9,11,12};

            System.out.println(firstMissingPositive(nums));
        }
}
